#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>

using namespace std;

// 螺旋数组
class Solution
{
public:
    static constexpr int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    vector<int> spiralOrder(vector<vector<int>> &matrix)
    {
        if (matrix.size() == 0 || matrix[0].size() == 0)
            return {};
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n));
        int total = m * n;
        int row = 0, col = 0;
        vector<int> ans(total);
        int directionIndex = 0;
        for (int i = 0; i < total; i++)
        {
            ans[i] = matrix[row][col];
            visited[row][col] = true;

            // 下一个位置的坐标
            int next_row = row + directions[directionIndex][0];
            int next_col = col + directions[directionIndex][1];

            // 如果越界或者已经访问过，那么则换一个方向
            if (next_row < 0 || next_row >= m || next_col < 0 || next_col >= n || visited[next_row][next_col])
            {
                directionIndex = (directionIndex + 1) % 4;
            }

            // row和col更新为下一个位置的坐标
            row += directions[directionIndex][0];
            col += directions[directionIndex][1];
        }

        return ans;
    }
};

// 旋转图像
class Solution
{
public:
    void rotate(vector<vector<int>> &matrix)
    {
        // 对于矩阵中第 i 行的第 j 个元素，
        // 在旋转后，它出现在倒数第 i 列的第 j 个位置
        int m = matrix.size(), n = matrix[0].size();
        auto tmp = matrix;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                tmp[j][n - i - 1] = matrix[i][j];
            }
        }
        matrix = tmp;
    }
};

// 搜索二维矩阵II
class Solution
{
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target)
    {
        int m = matrix.size(), n = matrix[0].size();
        int i = 0, j = n - 1;
        while (i < m && j >= 0)
        {
            if (matrix[i][j] == target)
                return true;
            else if (matrix[i][j] < target)
                i++;
            else
                j--;
        }
        return false;
    }
};

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 相交链表
class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        // 使用哈希表
        if (headA == nullptr || headB == nullptr)
            return nullptr;
        unordered_set<ListNode *> hash;
        ListNode *cur = headA;
        while (cur)
        {
            hash.insert(cur);
            cur = cur->next;
        }
        cur = headB;
        while (cur)
        {
            if (hash.count(cur))
                return cur;
            cur = cur->next;
        }

        return nullptr;
    }
};

// 反转链表
class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *newhead = nullptr, *cur = head;
        while (cur)
        {
            ListNode *next = cur->next;
            cur->next = newhead;
            newhead = cur;
            cur = next;
        }

        return newhead;
    }
};

// 回文链表
class Solution
{
public:
    bool isPalindrome(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return true;

        // 找到链表前半部分的尾节点和返回后半部分
        ListNode *end = endofprev(head);
        ListNode *start = reverselist(end->next);

        // 判断是否回文
        ListNode *p1 = head, *p2 = start;
        bool result = true;
        while (result && p2)
        {
            if (p1->val != p2->val)
                result = false;
            p1 = p1->next;
            p2 = p2->next;
        }

        end->next = reverselist(start);
        return result;
    }

    // 如果是偶数个节点，返回的是靠左的节点
    ListNode *endofprev(ListNode *head)
    {
        ListNode *fast = head, *slow = head;
        while (fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    ListNode *reverselist(ListNode *head)
    {
        ListNode *newhead = nullptr, *cur = head;
        while (cur)
        {
            ListNode *next = cur->next;
            cur->next = newhead;
            newhead = cur;
            cur = next;
        }
        return newhead;
    }
};